// Tags:
#include <algorithm>
#include <cctype>
#include <cstdio>

typedef long long ll;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

const int N = 21, mod = 1e9 + 7;
int n, m, k, f[1 << N][N], bhd[N];

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen64("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen64("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("count.in", "r", stdin);
  freopen("count.out", "w", stdout);
#endif
#endif

  read(n), read(m), read(k);
  for (int i = 0, u, v; i < m; ++i) {
    --read(u), --read(v);
    bhd[u] |= 1 << v;
  }
  f[0][0] = 1;
  for (int i = 0, lim = 1 << n; i < lim; ++i) {
    for (int j = 0; j < n; ++j) {
      if (!((i >> j) & 1)) {
        int cnt = __builtin_popcount(i & bhd[j]);
        for (int h = 0; h <= k - cnt; ++h) {
          f[i | (1 << j)][h + cnt] += f[i][h];
          if (f[i | (1 << j)][h + cnt] >= mod) f[i | (1 << j)][h + cnt] -= mod;
        }
      }
    }
  }
  ll ans = 0;
  for (int i = 0; i <= k; ++i) {
    ans += f[(1 << n) - 1][i];
    if (ans >= mod) ans -= mod;
  }
  printf("%lld", ans);
  return 0;
}